class Solution {
public:
    string shortestPalindrome(string s) {
        if(s.size() == 0) return s;
        string ss;
        for(int i = 0;i < s.size();i++){
            ss += '#';
            ss += s[i];
        }
        ss += '#';
        vector<int> p(ss.size(),1);
        int r = 1;
        int c = 1;
        int left = 1;
      
        for(int i = 1;i < ss.size();i++){
            if(r > i){
                p[i] = min(r - i,p[2 * c - i]);
            }else{
                p[i] = 1;
            }
            while(i-p[i]>=0 && i+p[i]<ss.size() && ss[i-p[i]] == ss[i+p[i]]){
                p[i]++;
            }
            if(i - p[i] + 1 == 0){
                left = (2 * p[i] - 1 ) / 2;
            }
            if(i + p[i] > r){
                r = i + p[i];
                c = i;
            }
        }

        if(left == s.size()) return s;
        string ans = s.substr(left,s.size()-left);
        reverse(ans.begin(),ans.end());
        return ans + s;
    }
};
